The present invention relates to techniques for performing timing analysis of an integrated circuit design. More particularly, the present invention is suitable for performing timing analysis in further of establishing a layout of an integrated circuit.
Establishing a layout of an integrated circuit is typically achieved employing a placement tool. A placement tool is a software tool that facilitates locating circuit elements of an integrated circuit according to design parameters. One class of integrated circuit includes programmable circuit elements, referred to as logic blocks or logic elements, which may be programmed to implement desired logic functions. These are typically referred to as programmable integrated circuits. Examples of programmable integrated circuits include field programmable gate arrays (FPGAs), programmable logic devices (PLDs), programmable logic arrays (PLAs), configurable logic arrays and mask-programmable logic devices. Programmable integrated circuits can also contain hardwired circuit blocks that are not programmable. During placement, circuit elements are assigned to physical logic elements, and other circuit elements are associated with the integrated circuit. This is referred to as programming of the integrated circuit.
Programming of the integrated circuit is done according to the design parameters, which are expressed as a network of abstract logic elements. The abstract logic elements are mapped onto the physical logic elements of the integrated circuit. In this manner, the physical logic elements of the integrated circuit are associated with the logic functions of the abstract logic elements. The conversion process is referred to as synthesis. During synthesis, a routing process is employed to place the differing logic elements in electrical communication.
Typically, the design parameters include timing requirements that define various characteristics of signal propagation between the logic elements of the integrated circuit. Exemplary timing requirements include source and destination points for the signal and the maximum allowable source-to-destination delays for signal propagation. Additional constraints included in the design parameters, in addition to the timing requirements, may be present. For example, minimum allowable clock speeds for various logic elements may be defined.
Relative placement of the logic elements in a physical layout of the integrated circuit determines, in part, the signal propagation time between the source and the destination. As a result, it is desired to analyze the propagation time of signals in a particular design once the logic elements have been mapped to a physical layout. This is referred to as timing analysis. Timing analysis facilitates identifying maximum delay paths between selected sources and destinations for a give design, relative to constraint.
To that end, a timing graph is generated that includes nodes connect by edges. The nodes represent logic elements, and the edges represent electrical connection between the logic elements. Determined are slack and relative slack/slack ratio values, commonly referred to as slack values, for certain paths between selected sources and destinations. The slack values facilitate determining the location of logic elements in a physical layout of the design. Specifically, edges of the timing graph may be associated with the slack values. In this manner, the timing delay among a sequence of edges that define a path between a source and a destination may be calculated. Were the timing delay along the path to exceed the timing requirements of the design, the physical location of the logic elements associated with the design change to improve, or reduce, the timing delay.
Two basic techniques to undertake timing analysis includes breadth-first search (BFS) or depth-first search (DFS). BFS is more advantageous, compared to DFS, for minimizing the additional work required to visit nodes which are not relevant to a computation. A drawback with BFS, however, is that the same is memory intensive, requiring more memory than DFS. Although recursive DFS may ameliorate the memory required for the timing analysis, typically BFS requires a larger region of the netlist to be examined than DFS, resulting is relatively more computationally expensive technique than DFS.
An important task when performing timing analysis is determining how many traversals of the timing graph is required to process each timing requirement. For example, each timing requirement may result in multiple traversals of the timing graph due to other higher-priority timing requirements being associated with all or part of a path. As a result, two conflicting timing requirements may correspond to all or part of the edges placing a given source in signal communication with a given destination, referred to as a conflict. Prior art attempts to address timing graph conflicts involve expanding timing requirements into source-to-destination assignments and identify common sources or destinations for differing timing requirements to allow merging the source-to-destination assignments by looking for common sources or destinations. This approach has proved to time consuming and memory intensive. Furthermore, grouping timing requirements having common sources of destinations provides little information about the tining requirements associated therewith.
There is a need, therefore, of overcoming timing graph conflicts while avoiding the time consuming, memory intensive analysis of the prior art.